// 推排序, 快速排序, 归并排序, 计数排序

import { isSorted, randomArr } from "../util";

/**
 * 堆排序k
 * @param arr 
 */
const hs = (arr: number[]) => {
    let len = arr.length;

    // 不需要排序
    if (len < 2) return;

    /**
     * 下滤
     * @param n 
     */
    const down = (i = 0) => {
        // 非叶子节点数量
        const sizes = len >> 1;

        /**
         * 获取左孩子
         * @param i 
         */
        const getLeft = (i: number) => (i << 1) + 1;

        /**
         * 获取右孩子
         * @param i 
         */
        const getRight = (i: number) => (i << 1) + 2;


        /**
         * 获取左右孩子的最大值
         * @param l 
         * @param r 
         */
        const getMax = (l: number, r: number) => {
            // 右孩子r大于等于长度, 直接返回
            if (r >= len) return l
            const e1 = arr[l],
                e2 = arr[r];
            return e1 > e2 ? l : r;
        }

        while (i < sizes) {
            // 1. 获取左孩孩子的索引
            const li = getLeft(i),
                ri = getRight(i);

            // 2. 获取左右孩子的最大值
            const maxI = getMax(li, ri);

            // 3. 父亲和左右的最大值比较
            if (getMax(maxI, i) === i) {
                // 父亲比孩子大, 结束
                break;
            }

            // 4. 交换
            swap(maxI, i);

            // 5. 更换i
            i = maxI
        }

    }


    /**
     * 交换元素
     * @param l 
     * @param r 
     */
    const swap = (l: number, r: number) => {
        const tmp = arr[l];
        arr[l] = arr[r];
        arr[r] = tmp
    }

    // 1. 原地建堆 (对非叶子节点建堆即可)
    const sizes = (len >> 1) - 1
    for (let i = sizes; i >= 0; i--) {
        down(i)
    }

    // 2. 第一个元素不断和最后一个元素交换
    while (len > 1) {
        // 交换元素
        swap(0, --len);

        // 对0位置进行下滤
        down()
    }

}

/**
 * 快速排序
 * @param arr 
 */
const qs = (arr: number[]) => {
    const len = arr.length;

    // 不需要排序
    if (len < 2) return;

    /**
     * 创建锚点
     * @param s 
     * @param e 
     */
    const createPivot = (s = 0, e = len) => {
        // 少于两个, 不需要创建锚点了
        if (e - s < 2) return;

        // 1. 保存锚点
        const pivot = arr[s];

        /**
         * 和锚点比较大小
         * @param t 
         */
        const compare = (t: number) => arr[t] - pivot;

        /**
         * r替换l的位置
         * @param l 
         * @param r 
         */
        const replace = (l: number, r: number) => arr[l] = arr[r]

        let start = s,
            end = e - 1;

        while (start < end) {
            // 从后开始往前比较
            while (start < end) {
                // 小于锚点
                if (compare(end) < 0) {
                    // 替换start的位置
                    replace(start, end);

                    // 结束循环 
                    break;
                }
                end--;
            }

            // 从前开始往后比较
            while (start < end) {
                // 大于锚点
                if (compare(start) > 0) {
                    replace(end, start);
                    break;
                }
                start++
            }
        }

        // start | end的位置就是锚点最后的位置
        arr[end] = pivot;
        // 左边创建锚点
        createPivot(s, end);

        // 右边创建锚点
        createPivot(end + 1, e)

    }

    createPivot()



}


/**
 * 归并排序
 * @param arr 
 */
const ms = (arr: number[]) => {
    const len = arr.length;

    // 不需要排序
    if (len < 2) return;

    /**
     * 合并两个有序的数组
     * @param s 
     * @param m 
     * @param e 
     */
    const merge = (s: number, m: number, e: number) => {
        // 1. 拷贝左边的数组
        const leftArr = arr.slice(s, m);

        // 2. 确定ai, li, le, ri, re
        let ai = s,
            li = 0,
            le = m - s,
            ri = m,
            re = e;

        while (li < le && ri < re) {
            if (arr[ri] < leftArr[li]) {
                // 右 < 左
                arr[ai] = arr[ri++];
            } else {
                // 右 >= 左
                arr[ai] = leftArr[li++];
            }
            ai++;
        }

        // 右边先结束
        if (ri >= re) {
            // 左边的拷贝到数组中去
            for (let i = li; i < le; i++) {
                arr[ai++] = leftArr[i]
            }
        }
    }

    const sort = (s = 0, e = len) => {
        if (e - s < 2) return;

        // 获取中间索引
        const m = (s + e) >> 1;

        // 左边
        sort(s, m);

        // 右边
        sort(m, e)

        // 合并
        merge(s, m, e)

    }

    sort()
}

/**
 * 计数排序
 * @param arr 
 */
const cs = (arr: number[]) => {
    const len = arr.length;
    // 不需要排序
    if (len < 2) return;

    let max = arr[0],
        min = arr[0];
    
    // 1. 获取最大最小值    
    for (let i = 1; i < len; i++) {
        if (arr[i] >= max) max = arr[i];

        if (arr[i] < min) min = arr[i]
    }

    // 2. 创建新数组
    const countArr = new Array(max - min + 1).fill(0);

    // 3. 对每一项进行计数
    for (let i = 0; i < len; i++) {
        countArr[arr[i] - min]++
    }

    // 4. 对前一项的数进行累加
    const cLen = countArr.length;
    for (let i = 1; i < cLen; i++) {
        countArr[i] += countArr[i - 1];
    }


    // 5 移动到新数组
    const newArr = new Array(len);
    for (let i = len - 1; i >= 0; i--) {
        newArr[--countArr[arr[i] - min]] = arr[i]
    }

    // 6. 更改arr
    for (let i = 0; i < len; i++) {
        arr[i] = newArr[i]
    }
}


// const arr = randomArr(0, 100, 90);
// hs(arr);
// console.log(isSorted(arr));

// const arr = randomArr(0, 100, 90);
// qs(arr);
// console.log(isSorted(arr));

// const arr = randomArr(0, 100, 90);
// ms(arr);
// console.log(arr);
// console.log(isSorted(arr));

const arr = randomArr(0, 100, 90);
cs(arr);
console.log(arr);
console.log(isSorted(arr));